package string.滑动窗口;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * @Author kaho
 * @create 2020/11/26
 */
public class _30_串联所有单词的子串 {

    /**
     * 给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
     * <p>
     * 注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。
     * <p>
     *  
     * <p>
     * 示例 1：
     * <p>
     * 输入：
     * s = "barfoothefoobarman",
     * words = ["foo","bar"]
     * 输出：[0,9]
     * 解释：
     * 从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。
     * 输出的顺序不重要, [9,0] 也是有效答案。
     * 示例 2：
     * <p>
     * 输入：
     * s = "wordgoodgoodgoodbestword",
     * words = ["word","good","best","word"]
     * 输出：[]
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     *
     * @param s
     * @param words
     * @return
     */
    public static List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList<Integer>();
        int wordNum = words.length;
        if (wordNum == 0) {
            return res;
        }
        int wordLen = words[0].length();
        //HashMap1 存所有单词
        HashMap<String, Integer> allWords = new HashMap<String, Integer>();
        for (String w : words) {
            int value = allWords.getOrDefault(w, 0);
            allWords.put(w, value + 1);
        }
        //遍历所有子串
        for (int i = 0; i < s.length() - wordNum * wordLen + 1; i++) {
            //HashMap2 存当前扫描的字符串含有的单词
            HashMap<String, Integer> hasWords = new HashMap<String, Integer>();
            int num = 0;
            //判断该子串是否符合
            while (num < wordNum) {
                String word = s.substring(i + num * wordLen, i + (num + 1) * wordLen);
                //判断该单词在 HashMap1 中
                if (allWords.containsKey(word)) {
                    int value = hasWords.getOrDefault(word, 0);
                    hasWords.put(word, value + 1);
                    //判断当前单词的 value 和 HashMap1 中该单词的 value
                    if (hasWords.get(word) > allWords.get(word)) {
                        break;
                    }
                } else {
                    break;
                }
                num++;
            }
            //判断是不是所有的单词都符合条件
            if (num == wordNum) {
                res.add(i);
            }
        }
        return res;

    }

    public static void main(String[] args) {
        String s = "barfoothefoobarman";
        String[] words = {"foo", "bar"};

        List<Integer> substring = findSubstring1(s, words);
    }


    public static List<Integer> findSubstring1(String s, String[] words) {
        List<Integer> r = new ArrayList<>();
        if (words.length == 0) {
            return r;
        }
        HashMap<String, Integer> words2Count = new HashMap<>();
        for (String word : words) {
            Integer count = words2Count.getOrDefault(word, 0);
            words2Count.put(word, ++count);
        }
        int wordLength = words[0].length();
        for (int i = 0; i < s.length() - words.length * wordLength+1; i++) {
            HashMap<String, Integer> curMap = new HashMap<>();
            int nums = 0;
            while (nums < words.length) {
                String word = s.substring(i + wordLength * nums, i + wordLength  * (nums+1));
                if (words2Count.containsKey(word)) {
                    Integer count = curMap.getOrDefault(word, 0);
                    curMap.put(word, ++count);
                    if (count > words2Count.get(word)) {
                        break;
                    }
                    nums++;
                }else {
                    break;
                }
            }
            if (nums == words.length) {
                r.add(i);
            }
        }
        return r;
    }
}
